//------------------------------------------------------------------------------
#include <QStringList>
#include <QTextStream>
#include <QtDebug>
#include "CDiff.h"
//------------------------------------------------------------------------------
#define MIN(a,b) ((a)<(b) ? (a) : (b))
//------------------------------------------------------------------------------
QString CDiff::diff(QString text1, QString text2)
{
	int N , M, Nt, Mt, size, x, y;
	QStringList listText1=text1.split("\n");
	QStringList listText2=text2.split("\n");
	QList<CDiffResult *> result;
	int *map;
	CDiffResult *lastResult=0;
	char lastAction=' ';
	QString ret="";
	QString sep="";
	
	N=listText1.count();
	M=listText2.count();
	
	if(N == 0 || M == 0)
	{
		if(N == 0)
		{
			lastResult=new CDiffResult('a');
			
			lastResult->setFromDest(0);
			lastResult->setToDest(M-1);
			lastResult->setFromSource(0);
		}else {
			lastResult=new CDiffResult('b');
			
			lastResult->setFromSource(0);
			lastResult->setToSource(N-1);
		}
		
		result.append(lastResult);
	}else 
	{
		Nt=N+1;
		Mt=M+1;
		size=Nt*Mt;
		
		map=new int[size];
		memset(map, 0, size*sizeof(int));
		
		for(x=0;x<Nt;x++)
		{
			map[x]=x;
		}
		
		for(y=0;y<Mt;y++)
		{
			map[y*Nt]=y;
		}
		
		for(y=0;y<M;y++)
		{
			for(x=0;x<N;x++)
			{
				int idx=(y+1)*Nt+(x+1);
				if(listText1.at(x) == listText2.at(y))
				{
					map[idx]=map[idx-Nt-1];
				}else
				{
					map[idx]=MIN(map[idx-1], map[idx-Nt])+1;
				}
			}
		}
		
		y=M;
		x=N;
		
		while(y || x)
		{	
			int idx=y*Nt+x;
			int v=map[idx];
			
			if(map[idx-1] < v)
			{
				x--;
				if(lastAction != 'd')
				{
					lastResult=new CDiffResult('d');
					
					lastResult->setFromSource(x);
					lastResult->setToSource(x);
					
					lastAction='d';
					
					result.append(lastResult);
				}else {
					lastResult->setFromSource(lastResult->getFromSource()-1);
				}
			}else if(map[idx-Nt] < v)
			{
				y--;
				if(lastAction != 'a')
				{
					lastResult=new CDiffResult('a');
					
					lastResult->setFromDest(y);
					lastResult->setToDest(y);
					lastResult->setFromSource(x);
					
					lastAction='a';
					
					result.append(lastResult);
				}else {
					lastResult->setFromDest(lastResult->getFromDest()-1);
				}
			}else if(map[idx-Nt-1] == v)
			{
				lastAction=' ';
				y--;
				x--;
			}
		}
		
		delete map;
	}
	
	for(int i=0;i<result.count();i++)
	{
		CDiffResult *p=result.at(i);
		int j;
		
		switch(p->getAction())
		{
			case 'a':
				ret+=sep+"a "+QString::number(p->getFromSource());
				sep="\n";
				for(j=p->getFromDest();j<=p->getToDest();j++)
				{
					ret+=sep+"> "+listText2.at(j);
				}
				break;
			case 'd':
				ret+=sep+"d "+QString::number(p->getFromSource())+" "+QString::number(p->getToSource());
				sep="\n";
				for(j=p->getFromSource();j<=p->getToSource();j++)
				{
					ret+=sep+"< "+listText1.at(j);
				}
				break;
		}
		
		delete p;
	}
	
	return ret;
}
//------------------------------------------------------------------------------
QString CDiff::merge(QString text, QString with)
{
	QStringList ret=text.split("\n");
	QStringList listWith=with.split("\n");
	int i=0;
	
	while(i<listWith.count())
	{
		char action;
		int from, to;
		unsigned idx;
		QString line=listWith.at(i);
		QTextStream textIStream(&line, QIODevice::ReadOnly);
		
		textIStream >> action >> from >> to;
		
		switch(action)
		{
			case 'd':
				idx=from;
				i++;
				do
				{
					ret.removeAt(from);
					i++;
				}while(i<listWith.count() && listWith.at(i)[0] == '<');
				break;
			case 'a':
				idx=from;
				i++;
				do
				{
					line=listWith.at(i);
					ret.insert(idx, line.remove(0, 2));
					idx++;
					i++;
				}while(i<listWith.count() && listWith.at(i)[0] == '>');
				break;
			default:
				i++;
				
		}
	}
	
	return ret.join("\n");
}
//------------------------------------------------------------------------------